package chapter26;

import java.util.*;

/**
 * 最大流-Ford-Fulkerson
 */
public class FordFulkerson {

    public static Graph fordFulkerson(Graph G, EdgeNode s, EdgeNode t) throws CloneNotSupportedException {
        for (VertexNode vertexNode : G.adjList) {
            EdgeNode u = vertexNode.firstEdge;
            EdgeNode v = u.next;
            while (v != null) {
                v.f = v.c;
                v = v.next;
            }
        }
        Graph Gf = (Graph) G.clone();
        fordFulkerson(Gf, s, t, s);
        while (access) {
            // find edge
            List<EdgeNode> path = new ArrayList<>();
            EdgeNode u1 = t.p;
            EdgeNode v1 = t;
            while (v1.key != s.key) {
                EdgeNode v2 = G.adjList.get(u1.adj).firstEdge.next;
                while (v2 != null) {
                    if (v2.key == v1.key) {
                        path.add(v2);
                        break;
                    }
                    v2 = v2.next;
                }
                v1 = u1;
                u1 = u1.p;
            }

            int cf = Integer.MAX_VALUE;
            for (EdgeNode p : path) {
                cf = Math.min(cf, p.f);
            }
            for (EdgeNode p : path) {
                // f 剩余最大通行容量
                p.f -= cf;
                if (p.original) {

                    EdgeNode u = G.adjList.get(p.adj).firstEdge;
                    while (u.next != null && u.next.key != p.firstEdge.key) {
                        u = u.next;
                    }
                    if (u.key == p.key || u.next == null) {
                        EdgeNode v = new EdgeNode(p.firstEdge.key, p.firstEdge.adj);
                        v.original = false;
                        if (p.f != p.c) {
                            v.f = cf;
                        }
                        insert(u, v, p.c);
                    } else {
                        u.next.f += cf;
                    }
                } else {
//                    p.f += cf;

                    EdgeNode u = G.adjList.get(p.firstEdge.adj).firstEdge;
                    while (u.next != null && u.next.key != p.key) {
                        u = u.next;
                    }
                    if (u.key == p.key || u.next == null) {
                        EdgeNode v = new EdgeNode(p.firstEdge.key, p.firstEdge.adj);
                        v.original = false;
                        if (p.f != p.c) {
                            v.f = cf;
                        }
                        insert(u, v, p.c);
                    } else {
                        u.next.f -= cf;
                    }
                }
            }

            // 重置
            for (VertexNode vertex : G.adjList) {
                vertex.firstEdge.visited = false;
                vertex.firstEdge.p = null;
            }
            t.p = null;
            access = false;
            fordFulkerson(Gf, s, t, s);
        }
        return Gf;
    }

    private static boolean access = false;

    private static void fordFulkerson(Graph G, EdgeNode s, EdgeNode t, EdgeNode su) {
        if (su.key == t.key) {
            // 可达
            access = true;
            return;
        }
        // 遍历
        EdgeNode v = su.next;
        while (v != null) {
            EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
            if (!v1.visited && v.f > 0) {
                v1.visited = true;

                v1.p = su;
                fordFulkerson(G, s, t, v1);
            }
            v = v.next;
        }
        su.visited = true;
    }

    public static void insert(EdgeNode x, EdgeNode y, int c) {
        EdgeNode pre = x;
        while (pre.next != null) {
            pre = pre.next;
        }
        y.firstEdge = x;
        y.c = c;
        pre.next = y;
    }

    public static class EdgeNode implements Cloneable {
        public char key;
        public EdgeNode firstEdge = this;
        public EdgeNode next;
        public int adj;
        public EdgeNode p;
        public int f;
        public int c;
        public boolean original = true;
        public boolean visited;

        public EdgeNode(char key, int adj) {
            this.key = key;
            this.adj = adj;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EdgeNode edgeNode = (EdgeNode) o;
            return Objects.equals(key, edgeNode.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

        @Override
        public String toString() {
            return "EdgeNode{" +
                    "key=" + key +
                    ", f=" + f +
                    ", c=" + c +
                    ", o=" + original +
                    '}';
        }

        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }
    }

    public static class VertexNode implements Cloneable {
        public String key;
        public EdgeNode firstEdge;

        public VertexNode(EdgeNode firstEdge) {
            this.firstEdge = firstEdge;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "key='" + key + '\'' +
                    ", firstEdge=" + firstEdge +
                    '}';
        }

        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }
    }

    public static class Graph implements Cloneable {
        public List<VertexNode> adjList = new ArrayList<>();
        public int numVertexes;
        public int numEdges;

        @Override
        public String toString() {
            return "Graph{" +
                    "adjList=" + adjList +
                    ", numVertexes=" + numVertexes +
                    ", numEdges=" + numEdges +
                    '}';
        }

        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }
    }

}
